This invention relates to the analysis and testing of data streams, primarily although not exclusively data contained in data packets in a communication network, whereby to develop mainly statistical or control information for use in the management of the network.
A primary usage of the invention would be in a processor which is adapted to receive information from a variety of sources, such as audio sources, telephone, television, local area networks and others, providing streams of information, normally in data packets which may assume a variety of forms, and prepares those packets, by modification of the packets, particularly in relation to header information, for transmission over a common medium, such as a synchronous transfer mode link whereby the data packets are transmitted over a plurality of virtual circuits (defined by the segmenting and switching operation of an asynchronous transfer mode switch) to a variety of receivers wherein the packets are distributed to their ultimate destinations. The processor could but need not be one that performs a bidirectional function acting both as a receiver and ATM transmitter as well as an ATM receiver and distributor of the packets.
It is a practical necessity in communication systems generally, and certainly of the type just mentioned, to provide temporary storage of data packets in a fairly high volume random access memory, normally a dynamic random access memory in order to provide rapid reading and retrieval operations. It is known quite widely to organise such a memory into a multiplicity of buffers each capable of containing data corresponding to a substantial number of data packets and to control the reading and writing of data to and from the buffers by means of software conveniently termed pointer tables which indicate the order in which buffers will be read and also indicate which buffers are available.
Organisation of the storage of data in this manner is a practical necessity owing to the large variety of possible sources and rates of communication of data which those sources may provide, the different priorities of data or data channels and so on.
Commonly, for example, data packets received at a processor of this kind need data processing for each packet, for example the examination of the address data (such as MAC address) so that it may be allotted to appropriate communication channels according to whether it is a uni-cast message (intended for a specific destination), a multi-cast message (intended for a specified plurality of destinations) or a broadcast message, and so on.
It is desirable to analyse the control data or destination data in the data packets in order to obtain statistical information which will assist the management of data flow in the network to determine, for example, whether there is an undue proportion of defective data packets. It is also desirable to be able to add offsets to data values to assist in examining different pointers of a data packet for statistical collection purposes. These and other operations may be performed by a data processor but the large volume of data normally handled by a system of this nature makes the consumption of ordinary data processing time undesirable owing partly to the difficulty of providing sufficient processing power and partly to the increased latency that would be produced.
The present invention is one aspect of an improved technique by means of which buffer data can be analysed more efficiently.
The first of the co-pending applications of previous mention concerns a technique comprising reading buffer data and applying to data packets appearing sequentially in the data a group of instructions which independently test data of the data packets in turn. That is to say, the instruction stream, which may be customised according to preference, is a selection from a larger set of tests or instructions. The advantage of this technique is that it is feasible to perform rapid statistical analysis of a large number of data packets, without full examination or processing of those packets. One may determine, for example, how many packets are being transferred in a given interval from an identified source to an identified location and determine the kind of packet.
Further, one may build a protocol distribution tree. Such network management information is used for the analysis known as RMON1 and RMON2 in the IEEE network standards.
The present invention particularly concerns the management of data stacks in such a technique and more generally.
A method of processing data according to the invention generally comprises providing a program of selected microcode instructions of which at least one prescribes a test on a data pattern in a data packet, subjecting a multiplicity of said data packets to said program including said test, pushing a result of each said test onto a last-in first-out temporary storage stack, performing a combinational logic operation on all the results in said stack, removing all said results from said stack, and pushing the resultant of said logic operation onto said stack. Preferably all said results are removed from said stack in one operation, and said resultant is pushed onto said stack in the same operation.
A last-in first-out data stack according to the invention is able to store a plurality (n) of elements wherein the plurality is greater than two and comprising for each of n storage locations in the stack a selector means adapted to receive n elements read out from the stack and a new element, the selector means being arranged to make a controllable selection of its received elements and combinational logic capable of performing logic manipulations on said selection of elements, and providing a resultant for pushing onto said stack.